\documentclass[%
    %draft,
    %submission,
    %compressed,
    a4paper,
    %12pt,
    10pt,
    final,
    %technote,
    %internal,
    %submitted,
    %inpress,
    %reprint,
    %titlepage,
    notitlepage,
    %anonymous,
    narroweqnarray,
    inline,
    oneside,
    %invited,
    %conference
    article
    ]{ieee}

%\documentclass[a4paper,12pt]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{epstopdf}

\newcommand{\latexiie}{\LaTeX2{\Large$_\varepsilon$}}

%\usepackage{ieeetsp}    % if you want the "trans. sig. pro." style
%\usepackage{ieeetc}    % if you want the "trans. comp." style
%\usepackage{ieeeimtc}    % if you want the IMTC conference style

% Use the `endfloat' package to move figures and tables to the end
% of the paper. Useful for `submission' mode.

%\usepackage {endfloat}

% Use the `times' package to use Helvetica and Times-Roman fonts
% instead of the standard Computer Modern fonts. Useful for the
% IEEE Computer Society transactions.
%\usepackage{times}
% (Note: If you have the commercial package `mathtime,' (from
% y&y (http://www.yandy.com), it is much better, but the `times'
% package works too). So, if you have it...
%\usepackage {mathtime}

% for any plug-in code... insert it here. For example, the CDC style...
%\usepackage{ieeecdc}

\begin{document}

\title[]{
	Trabajo practico 1\\
	Algoritmos de b\'usqueda}

\author{
     Luciano Mangiarotti (I.T.B.A),
\and Federico Santos (I.T.B.A),
\and Jimena Pose (I.T.B.A) \\ \\ }

\maketitle

\section{Introducci\'on}

\noindent El objetivo de este trabajo es utilizar distintos algoritmos de b\'usqueda informados y desinformados 
para resolver el problema asignado y analizar los resultados a partir de las caracter\'isticas de cada uno de los algoritmos.\\

\noindent El problema a resolver es el juego llamado \textit{CalcuDoku} \cite{1}. El mismo consiste en un tablero 
cuadrado de dimensi\'on $N$ que se debe completar con n\'umeros enteros entre 1 y $N$ cumpliendo las siguientes restricciones: \\

\begin{itemize}
  \item No puede repetirse el mismo entero en una fila.
  \item No puede repetirse el mismo entero en una columna.
  \item Deben cumplirse las restricciones aritm\'eticas indicadas en el tablero. \\
\end{itemize}

\noindent Las restricciones aritm\'eticas se aplican a grupos de celdas adyacentes, exigiendo que el resultado de 
aplicar una operaci\'on a dichas celdas sea igual a un valor dado.\\

\noindent Las operaciones aceptadas son la suma y el producto. Una celda puede formar parte de un solo grupo. Por ejemplo, 
los valores en $(0,0)$, $(0,1)$ y $(0,2)$ deben sumar $4$.\\

\noindent Los algoritmos de b\'usqueda desinformados a utilizar son \textit{DFS}, \textit{BFS} y \textit{Profundizaci\'on iterativa}. Como algoritmos de 
b\'usqueda informados se utilizan \textit{A*} y \textit{Greedy Search}. \\

\noindent En la Secci\'on II se describe el problema a resolver y la forma en que se modela computacionalmente para su soluci\'on. 
Se explican las reglas que se aplican, as\'i como tambi\'en la funci\'on de costo y las heur\'isticas utilizadas en los algoritmos 
de b\'usqueda informados. \\

\noindent En la Secci\'on III se describen los tableros que se usar\'an para realizar las distintas pruebas que constituyen este trabajo.\\

\noindent En la Secci\'on IV se muestran los resultados obtenidos con los distintos m\'etodos de b\'usqueda y se sacan conclusiones 
sobre dichos resultados, por \'ultimo, en la Secci\'on V se presentan los comentarios finales.

\section{Presentaci\'on del problema}

\noindent Para el desarrollo de este trabajo es importante analizar los estados y las reglas a utilizar. Una representaci\'on 
eficiente de los estados es clave para resolver tableros grandes en los que se debe explorar una gran cantidad de estados. 

\noindent Cada estado se representa con una matriz de enteros de $N \times N$ celdas. Dos estados son iguales cuando tienen los mismos 
enteros en ex\'actamente la misma posici\'on del tablero. \\

\noindent El estado inicial del problema es el tablero vac\'io y el estado final o estado \textit{goal} es el tablero con todas las celdas 
completas. \\

\noindent Por su parte, es importante que las reglas representen fielmente las caracter\'isticas del juego. En este problema la 
cantidad de reglas var\'ia de acuerdo a la dimensi\'on del tablero. \\

\noindent En particular, la cantidad de reglas va a ser igual a $N^3$, ya que $N^2$ es la cantidad de celdas del tablero y a su 
vez $N$ es la cantidad de enteros que se pueden poner en una celda. A continuaci\'on se enumeran las 8 reglas correspondientes 
a un tablero de $2 \times 2$: \\

\begin{itemize}
  \item Poner un 1 en la casilla [0,0] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 2 en la casilla [0,0] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 1 en la casilla [0,1] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 2 en la casilla [0,1] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 1 en la casilla [1,0] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 2 en la casilla [1,0] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 1 en la casilla [1,1] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna.
  \item Poner un 2 en la casilla [1,1] siempre y cuando este vac\'ia, cumpla las restricciones aritm\'eticas y no se repita en una fila o columna. \\
\end{itemize}

\noindent De la misma forma, en un tablero de $3 \times 3$ se tienen 27 reglas, mientras que en uno de $4 \times 4$ se tienen 64. \\

\noindent Los algoritmos de b\'usqueda informados hacen uso de una funci\'on de costo y/o heur\'isticas para mejorar 
la b\'usqueda de la soluci\'on. En las siguientes subsecciones se describen las heur\'isticas usadas para resolver los problemas, 
as\'i como tambi\'en la funci\'on de costo propuesta.

\subsection{Funci\'on de costo}

\noindent La m\'etrica usada para determinar el costo de la soluci\'on es la cantidad de valores insertados en el tablero. 
El estado inicial tiene costo igual a cero, ya que est\'a vac\'io. El costo de aplicar una regla es unitario e igual en todos los casos.\\

\noindent Luego, cada vez que se pone un nuevo valor en el tablero se incrementa en uno el costo total. De acuerdo a esta m\'etrica, 
el costo del estado \textit{goal} es igual a la cantidad de celdas que tiene el tablero, es decir $N^2$.\\

\subsection{Heur\'isticas}

\noindent A continuaci\'on se plantean distintas heur\'isticas que permitan mejorar la busqueda de la soluci\'on mediante el uso de 
algoritmos de b\'usqueda informados. Estas heur\'isticas se calculan en funci\'on de la distancia a la que se encuentra un determinado 
estado de la soluci\'on, o \textit{goal}. Cuanto m\'as cerca de la soluci\'on se est\'a, menor es el valor de $h(n)$, siendo $0$ en el 
estado final.

\subsubsection*{\textit{Primer Heur\'istica}}

\noindent Una posible primer heur\'istica para el presente problema consiste en determinar el valor de la funci\'on $h$ en dicho 
estado seg\'un la cantidad de bloques de restricciones aritm\'eticas que falten completar. \\

\noindent Por ejemplo, para un tablero con cuatro grupos de celdas, de los cuales s\'olo uno se encuentra completo, la funci\'on heur\'istica 
ser\'a $h(n) = 3$. A medida que se van completando los bloques, se est\'a m\'as cerca de la soluci\'on, y por lo tanto el valor de la funci\'on 
heur\'istica disminuye. \\

\noindent Para el estado \textit{goal}, como todos los grupos de celdas est\'an completos, se tiene $h(n) = 0$.

\subsubsection*{\textit{Segunda Heur\'istica}}

\noindent Una segunda heur\'istica posible para el presente problema consiste en determinar el valor de $h(n)$ de un estado de 
acuerdo a la cantidad de filas y columnas que falten completar. \\

\noindent En un tablero de $3 \times 3$ que se encuentra vac\'io (estado inicial) la heur\'istica es $h(n_0) = 6$, ya que ninguna de las filas 
o columnas est\'an completas. A medida que se van completando las celdas, se est\'a m\'as cerca de la soluci\'on, y por lo tanto el valor de 
la funci\'on heur\'istica disminuye. \\

\noindent Para el estado \textit{goal}, como todas las filas y columnas est\'an completas, se tiene $h(n) = 0$.

\subsubsection*{\textit{Tercer Heur\'istica}}

\noindent La tercer heur\'istica planteada consiste en calcular la cantidad de posibles reglas que aplican a cada una de las celdas, o 
sea, la cantidad de valores posibles que dicha celda puede tomar. \\

\noindent El valor de la heur\'istica consiste en la suma de los valores posibles que tiene cada una de las celdas del tablero, sumado a la 
cantidad de celdas libres que tiene el tablero. \\

\noindent En el estado inicial (tablero vac\'io) de un tablero de $3 \times 3$ son a lo sumo 3, siendo 9 la cantidad de celdas. A su vez 
las 9 celdas est\'an vac\'ias, por el valor de $h(n)$ va a ser a lo sumo $36$. \\

\noindent En el estado \textit{goal}, como todas las casillas est\'an completas, la cantidad de vac\'ios es nulo y ning\'un valor se 
puede aplicar. Por lo tanto $h(h_g) = 0$.

\section{Tableros}

\noindent En esta secci\'on se presentan los tableros que se resuelven y se utilizan para analizar el desempe\^no de los distintos 
algoritmos a lo largo de este informe.

\subsection*{Tablero 1:}

\noindent El primer tablero es uno de los m\'as peque\^nos se se pueden armar, con s\'olamente 4 celdas. Las restricciones de dicho 
tablero son las siguientes: \\

\begin{itemize}
	\item Las celdas $(0,0)$ y $(1,0)$ deben sumar 3.
	\item La celda $(0,1)$ debe valer 1.
	\item La celda $(1,1)$ debe valer 2. \\
\end{itemize}

\noindent La Figura (\ref{fig:tablero1}) muestra gr\'aficamente el aspecto de dicho tablero y su soluci\'on. Para la soluci\'on del mismo se debe 
generar un \'arbol de b\'usqueda de profundidad 4.

\subsection*{Tablero 2:}

\noindent El segundo tablero tiene dimensi\'on $N=3$ y se muestra en la Figura (\ref{fig:tablero2}). Las restricciones de dicho tablero son las siguientes: \\

\begin{itemize}
	\item Las celdas $(0,1)$, $(0,2)$ y $(1,2)$ deben sumar 7.
	\item Las celdas $(0,0)$, $(1,0)$ y $(1,1)$ deben sumar 5.
	\item Las celdas $(2,0)$, $(2,1)$ y $(2,2)$ deben sumar 6. \\
\end{itemize}

\noindent En este caso, el \'arbol de b\'usqueda tendr\'a profundidad 9.

\subsection*{Tablero 3:}

\noindent El tercer tablero tiene dimensi\'on $N=4$, por lo que tiene 16 celdas. Este tablero tiene las siguientes restricciones: \\

\begin{itemize}
	\item Las celdas $(0,0)$ y $(0,2)$ deben sumar 4.
	\item Las celdas $(0,2)$ y $(1,2)$ deben sumar 6.
	\item La celda $(0,3)$ debe valer 4.
	\item Las celdas $(1,0)$ y $(2,0)$ deben sumar 3.
	\item Las celdas $(1,1)$ y $(2,1)$ deben sumar 7.
	\item La celda $(2,2)$ debe valer 1.
	\item Las celdas $(1,3)$ y $(2,3)$ deben sumar 5.
	\item Las celdas $(3,0)$ y $(3,1)$ deben sumar 6.
	\item Las celdas $(3,2)$ y $(3,3)$ deben sumar 4. \\
\end{itemize}

\noindent La Figura (\ref{fig:tablero3}) muestra gr\'aficamente a dicho tablero y su soluci\'on. La b\'usqueda de la soluci\'on en 
este tablero genera un \'arbol de profundidad 16.

\subsection*{Tablero 4:}

\noindent El tablero m\'as grande que se intenta resolver es de dimensi\'on $N=5$, es decir, de 25 celdas. Las restricciones aritm\'eticas 
de dicho tablero de presentan a continuaci\'on: \\

\begin{itemize}
	\item La celda $(0;0)$ debe valer 2.
	\item La celda $(0;1)$ debe valer 3.
	\item El producto de las celdas $(0;2)$ y $(1;2)$ debe valer 5.
	\item El producto de las celdas $(0;3)$ y $(0;4)$ debe valer 4.
	\item El producto de las celdas $(1;0)$ y $(1;1)$ debe valer 10.
	\item El producto de las celdas $(2;0)$ y $(3;0)$ debe valer 3.
	\item La celda $(4;0)$ debe valer 4.
	\item El producto de las celdas $(2;1)$ y $(2;2)$ debe valer 4.
	\item El producto de las celdas $(3;1)$ y $(4;1)$ debe valer 20.
	\item El producto de las celdas $(3;2)$ y $(4;2)$ debe valer 6.
	\item El producto de las celdas $(1;3)$ y $(2;3)$ debe valer 20.
	\item El producto de las celdas $(1;4)$ y $(2;4)$ debe valer 6.
	\item El producto de las celdas $(3;3)$ y $(3;4)$ debe valer 15.
	\item El producto de las celdas $(4;3)$ y $(4;4)$ debe valer 2. \\
\end{itemize}

\noindent An\'alogamente a los tableros anteriores, la Figura (\ref{fig:tablero4}) muestra el aspecto de este tablero y su soluci\'on. El mismo genera 
un \'arbol de b\'usqueda para la soluci\'on con 25 niveles de profundidad.

\section{Resultados y Conclusiones}

\noindent A continuaci\'on se presentan los resultados obtenidos utilizando las distintas estrategias de b\'usqueda y heur\'isticas propuestas. Las 
pruebas se realizaron utilizando los tableros que se describen en la secci\'on anterior. \\

\noindent En las tablas, el uso de las siglas OOM significa que la ejecuci\'on finalizo por falta de memoria y TO significa 
que no se encontr\'o una soluci\'on en un tiempo prudencial (Por ejemplo, en m\'as de tres horas no se alcanzo la solucion).

\subsection*{Primera Prueba: Tablero 1}

\noindent La Tabla (\ref{tab:tabla1}) muestra un cuadro con los resultados obtenidos sobre los distintos algoritmos utilizados en la b\'usqueda de 
la soluci\'on de dimension $2 \times 2$. Dado que la soluci\'on se encuentra a profundidad 4, la cantidad de nodos a explorar es suficientemente 
chica como para que todos los algoritmos encuentren la soluci\'on en cuesti\'on de segundos. \\

\noindent Como era de esperarse, el algoritmo \textit{DFS} expande menor cantidad de nodos que los otros dos algoritmos desinformados. Esto se debe 
a que \textit{DFS} comienza expandiendo la rama donde est\'a la soluci\'on. \\

\noindent Por su parte, \textit{BFS} va expandiendo todos los nodos de todos los niveles recorriendo casi todo el \'arbol hasta completar el 
tablero. Profundizaci\'on iterativa se comporta de manera similar a \textit{BFS} aunque expande menos nodos. \\

\noindent Debido a las reducidas dimensiones del tablero, no se llega a apreciar una mejora considerable con el uso de algoritmos de b\'usqueda 
informados, aunque se observa que expanden menos nodos que \textit{BFS} y \textit{PI}. De todas formas, no se justifica hacer una poda en un
\'arbol de busqueda tan chico.

\subsection*{Segunda Prueba: Tablero 2}

\noindent La Tabla (\ref{tab:tabla2}) muestra un cuadro con los resultados obtenidos sobre los distintos algoritmos utilizados en la b\'usqueda 
de la soluci\'on para el tablero de $3 \times 3$. En este caso, las dimensiones del tablero siguen siendo lo suficientemente chicas para que 
cualquier estrategia pueda encontrar la soluci\'on. \\

\noindent Al igual que en el tablero de $2 \times 2$, el algoritmo \textit{DFS} expande una cantidad mucho menor de nodos que el resto de 
los algoritmos. Se observa tambi\'en la diferencia de tiempo de procesamiento, el cual es mas grande que en la primer prueba. \\

\noindent Cuando se usa \textit{Greedy  Search} el tiempo de procesamiento y la cantidad de nodos generados se reduce considerablemente. 
Esta mejora se da usando las heur\'isticas 1 y 2. \\

\noindent Esto se debe a que \textit{Greedy Search} selecciona el nodo de menor heur\'istica entre los reci\'en expandidos. Por lo tanto, si 
profundiza a trav\'es de la rama correcta llega a la soluci\'on expandiendo menor cantidad de nodos.

\subsection*{Tercera Prueba: Tablero 3}

\noindent La Tabla (\ref{tab:tabla3}) muestra un cuadro con los resultados obtenidos sobre los distintos algoritmos utilizados en la b\'usqueda 
de la soluci\'on para el tablero de $4 \times 4$. Las dimensiones de este tablero hacen que la diferencia entre los algoritmos de b\'usqueda 
informados y no informados resulte evidente. \\

\noindent Se observa claramente c\'omo los algoritmos de b\'usqueda informados generan una menor cantidad de estados y se ejecutan en menor 
tiempo. \\

\noindent Por otro lado, se observa que el algoritmo \textit{A*} utilizando la primer heur\'istica tiene una performance considerablemente 
superior al resto de los algoritmos. \\

\noindent Esto se debe a que el tablero contiene dos buckets de una sola celda, por lo tanto en el nivel 2 
del \'arbol de b\'usqueda va a haber un nodo con un valor de heu\'risita m\'as bajo que los dem\'as, haciendo que el 
algoritmo expanda esa rama. \\

\noindent La presencia \textit{buckets} con una sola celda hacen que \textit{A*} usando la heur\'istica 1 sea una 
mejor opci\'on frente a los algoritmos \textit{Greedy}, algo que no sucede en la prueba anterior, donde no hay \textit{buckets} simples.

\subsection*{Cuarta Prueba: Tablero 4}

\noindent Para tableros de dimensiones de $5 \times 5$, los algoritmos desinformados no logran encontrar la soluci\'on por falta de memoria. Por 
tal motivo, se resuelve el tablero \ref{fig:tablero4} usando los algoritmos de b\'usqueda informados. \\

\noindent Los resultados se muestran en la Tabla (\ref{tab:tabla4}). Se puede observar que la \'unica estrategia con la que se encuentra la 
soluci\'on es \textit{A*} con la heur\'istica 1. Esto se debe, en parte, a que el tablero contiene 3 \textit{buckets} con una \'unica 
celda. Por otra parte, la primer rama que se expande es la que contiene la soluci\'on. \\ 

\noindent Los dem\'as algoritmos y heur\'isticas hacen que el motor de b\'usqueda se quede sin memoria o que el tiempo de procesamiento 
sea excesivo. \\

\noindent El motivo por el que con el resto de los algoritmos no se encuentra la soluci\'on se debe a que al utilizar un tablero de 
estas dimensiones, el factor de ramificaci\'on y profundidad de la soluci\'on son considerablemente mayores que en los tableros anteriores. \\

\noindent Por lo tanto, si el motor de b\'usqueda expande una rama equivocada, el hecho de expandirla y realizar \textit{backtracking} 
genera un alto consumo de memoria ya que implica una gran cantidad de nodos expandidos. \\

\noindent Para analizar el caso en el que \textit{A*} usando la heur\'istica 1 comienza por la rama equivocada, proponemos el 
tablero \ref{fig:tablero5} que consiste en una variante del tablero \ref{fig:tablero4}. En particular se une la celda $(0,0)$ y la $(0,1)$ 
en un \'unico \textit{bucket} cuyo producto debe ser 6. En este tablero, resulta imposible obtener la soluci\'on con la memoria disponible. \\

\noindent Si las heur\'isticas no pueden diferenciar dos estados de los cuales uno conduce a una soluci\'on y el otro no, las posibilidades de 
encontrar la soluci\'on depede del orden de aplicacion de las reglas. \\

\noindent En particular, si las reglas hacen que se expanda primero el nodo que no conduce a la soluci\'on es altamente probable que no se 
pueda encontrar la soluci\'on. \\

\noindent Por este motivo, se propone aplicar aleatoriamente las reglas. Con esta modificacion, se pudo encontrar soluci\'on al tablero 
\ref{fig:tablero5} haciendo uso de \textit{A*} con la heur\'istica 1. Los resultados que se obtuvieron son los siquientes: \\

\begin{itemize}
	\item Nodos expandidos: 10774
	\item Nodos en frontera: 82572
	\item Estados generados: 93346
	\item Tiempo requerido: 26210 ms \\
\end{itemize}

\noindent Se puede decir que este cambio permiti\'o obtener una soluci\'on en este caso, pero dado que el orden en que se aplican las reglas 
es aleatorio, no se puede garantizar que siempre que se ejecute el algoritmo se encuentre una soluci\'on.

\section{Comentarios Finales}

\noindent Si bien la soluci\'on no es \'unica en todos los tableros, \'esta se encuentra siempre al mismo nivel. Por este motivo, no conviene 
usar el algoritmo  \textit{BFS}, ya que es imposible encontrar una soluci\'on que no est\'e en un nodo hoja y se recorren nodos 
innecesariamente. Se recomienda en cambio, el uso de \textit{DFS} como algoritmo de b\'usqueda desinformado. \\

\noindent A diferencia de otros problemas, como el \textit{problema del viajante}, el costo de todas las soluciones es el 
mismo. Por este motivo es equivalente encontrar una u otra y hace que no sea necesario encontrar una heuristica que sea admisible. \\

\noindent Respecto a los algoritmos de b\'usqueda informados, se puede decir que para este problema la efectividad de los mismos depende, en 
parte, del orden de aplicaci\'on de las reglas. \\

\noindent Resulta complicado encontrar una heur\'istica que expanda una cantidad de nodos tal que permita garantizar un 
resultado satisfactorio para cualquier tablero en un tiempo razonable con la memoria disponible. \\

\begin{thebibliography}{1}
    \bibitem [1]{1} \textit{http://www.conceptispuzzles.com/index.aspx?uri=puzzle/calcudoku}
\end{thebibliography}

\clearpage

\begin{figure*}
	\centering
		\includegraphics[scale=0.4]{tablero1.PNG}
	\caption{Tablero 1 - Dimensi\'on $2 \times 2$. Los n\'umeros en la esquina superior corresponden a las restricciones matem\'aticas.}
	\label{fig:tablero1}
\end{figure*}

\begin{figure*}
	\centering
		\includegraphics[scale=0.4]{tablero2Vacio.PNG}
	\caption{Tablero 2 - Dimensi\'on $3 \times 3$. Los n\'umeros en la esquina superior corresponden a las restricciones matem\'aticas.}
	\label{fig:tablero2}
\end{figure*}

\begin{figure*}
	\centering
		\includegraphics[scale=0.4]{tablero3Vacio.PNG}
	\caption{Tablero 3 - Dimensi\'on $4 \times 4$. Los n\'umeros en la esquina superior corresponden a las restricciones matem\'aticas.}
	\label{fig:tablero3}
\end{figure*}

\begin{figure*}
	\centering
	\includegraphics[scale=0.4]{tablero4Vacio.PNG}
	\caption{Tablero 4 - Dimensi\'on $5 \times 5$. Los n\'umeros en la esquina superior corresponden a las restricciones matem\'aticas.}
	\label{fig:tablero4}
\end{figure*}

\begin{figure*}
	\centering
	\includegraphics[scale=0.4]{tablero5Vacio.PNG}
	\caption{Tablero 5 - Dimensi\'on $5 \times 5$. Los n\'umeros en la esquina superior corresponden a las restricciones matem\'aticas.}
	\label{fig:tablero5}
\end{figure*}

\begin{table*}
	\centering
    \begin{tabular}{l c c c c c c c c c}
    \hline
    \hline
    & \textbf{DFS} & \textbf{BFS} & \textbf{PI} & \textbf{A*} & \textbf{A*} & \textbf{A*} & \textbf{GS} & \textbf{GS} & \textbf{GS}\\
    \hline
    \hline \\
    \textbf{Heur\'istica} & - & - & - & H1 & H2 & H3 & H1 & H2 & H3\\
    \textbf{Nodos expandidos} & 4 & 20 & 28 & 4 & 4 & 9 & 4 & 7 & 9\\
    \textbf{Nodos en frontera} & 9 & 0 & 9 & 9 & 9 & 6 & 9 & 7 & 6\\
    \textbf{Tiempo Proc.} & 5 ms & 7 ms & 9 ms & 6 ms & 4 ms & 7 ms & 6 ms & 6 ms & 7 ms\\
    \textbf{Estados generados} & 13 & 20 & 53 & 13 & 13 & 15 & 13 & 14 & 15\\ \\
    \hline
    \end{tabular}
	\caption{Resultados obtenidos para el Tablero (\ref{fig:tablero1}) usando las distintas estrategias de b\'usqueda.}
	\label{tab:tabla1}
\end{table*}

\begin{table*}
	\centering
    \begin{tabular}{l c c c c c c c c c}
    \hline
    \hline
    & \textbf{DFS} & \textbf{BFS} & \textbf{PI} & \textbf{A*} & \textbf{A*} & \textbf{A*} & \textbf{GS} & \textbf{GS} & \textbf{GS}\\
    \hline
    \hline \\
    \textbf{Heur\'istica} & - & - & - & H1 & H2 & H3 & H1 & H2 & H3\\
    \textbf{Nodos expandidos} & 1635 & 7096 & 29441 & 462 & 1867 & 3010 & 9 & 22 & 1785\\
    \textbf{Nodos en frontera} & 82 & 1 & 82 & 2937 & 3436 & 60 & 83 & 81 & 62\\
    \textbf{Tiempo Proc.} & 414 ms & 982 ms & 2857 ms & 214 ms & 560 ms & 608 ms & 12 ms & 14 ms & 427 ms\\
    \textbf{Estados generados} & 1717 & 7097 & 37420 & 1400 & 5303 & 3070 & 92 & 103 & 1874\\ \\
    \hline
    \end{tabular}
	\caption{Resultados obtenidos para el Tablero (\ref{fig:tablero2}) usando las distintas estrategias de b\'usqueda.}
	\label{tab:tabla2}
\end{table*}

\begin{table*}
	\centering
    \begin{tabular}{l c c c c c c c c c}
    \hline
    \hline
     & \textbf{DFS} & \textbf{BFS} & \textbf{PI} & \textbf{A*} & \textbf{A*} & \textbf{A*} & \textbf{GS} & \textbf{GS} & \textbf{GS}\\
    \hline
    \hline \\
    \textbf{Heur\'istica} & - & - & - & H1 & H2 & H3 & H1 & H2 & H3\\
    \textbf{Nodos expandidos} & 678274 & 2485575 & TO & 18 & TO & 1143237 & 53990 & 508800 & 1519228\\
    \textbf{Nodos en frontera} & 268 & 0 & TO & 315 & TO & 173 & 293 & 280 & 169\\
    \textbf{Tiempo Proc.} & 136423 ms & 687333 ms & TO & 68 ms & TO & 288592 ms & 8509 ms & 99267 ms & 363291 ms\\
    \textbf{Estados generados} & 678542 & 2485575 & TO & 333 & TO & 1143410 & 54283 & 509080 & 1519397\\ \\
    \hline
    \end{tabular}
	\caption{Resultados obtenidos para el Tablero (\ref{fig:tablero3}) usando las distintas estrategias de b\'usqueda.}
	\label{tab:tabla3}
\end{table*}

\begin{table*}
	\centering
    \begin{tabular}{l c c c c c c c}
    \hline
    \hline
     	& \textbf{A*} & \textbf{A*} & \textbf{GS} & \textbf{GS} \\
    \hline
    \hline \\
			\textbf{Heur\'istica} & H1 & H2/H3 & H1 & H2/H3	\\
			\textbf{Nodos expandidos} & 978 & OOM & TO & OOM \\
			\textbf{Nodos en frontera} & 6262 & OOM & TO & OOM \\
			\textbf{Tiempo Proc.} & 744 ms & OOM & TO & OOM \\
			\textbf{Estados generados} & 7240 & OOM & TO & OOM \\ \\
    \hline
    \end{tabular}
	\caption{Resultados obtenidos para el Tablero (\ref{fig:tablero4}) usando las distintas estrategias de b\'usqueda.}
	\label{tab:tabla4}
\end{table*}


\end{document}
